package q1640_canFormArray;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    /*
    由于题目中明确了数组中都是互不相同的数字
    因此可以用hash表来解决该题 可以对每一个piece的key设置为它的第一个数字
    然后维护一个idx 从arr的第一个开始找 如果找到map中有对应的数字
    代表找到了一个碎片段的一个开头，接下来开始依次比较 如果有不同就说明不对
    然后比较完后idx来到下一个碎片的开头，继续查找map中有没有对应的数字
    直到最后比较完毕
     */
    public boolean canFormArray(int[] arr, int[][] pieces) {
        Map<Integer, int[]> map = new HashMap<>();
        for (int[] piece : pieces) map.put(piece[0], piece);
        int idx = 0;
        while (idx < arr.length) {
            if (map.containsKey(arr[idx])) {
                int[] cur = map.get(arr[idx]);
                for (int i = 0; i < cur.length; i++, idx++) {
                    if (arr[idx] != cur[i]) return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }
}
